package com.kingwood.algorithm.zuochengyun.chafen;

import java.util.Arrays;

/**
 * @Author 22025812
 * @Description:
 * // 最强祝福力场
 * // 小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"
 * // 而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场
 * // 经过不断的勘测记录，小扣将所有力场的分布都记录了下来
 * // forceField[i] = [x,y,side]
 * // 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。
 * // 若任意一点的 力场强度 等于覆盖该点的力场数量
 * // 请求出在这片地带中 力场强度 最强处的 力场强度
 * // 注意：力场范围的边缘同样被力场覆盖。
 * // 测试链接 : https://leetcode.cn/problems/xepqZ5/
 * @Date: 2024/3/12 14:18
 * @Modified By：
 * @Version 1.0
 */
public class Code05_StrongestForceField {
    public static int fieldOfGreatestBlessing(int[][] fields) {
        int n = fields.length;
        // n 矩形的个数，x,y 各有2*n 个坐标
        long[] xs = new long[n<<1];
        long[] ys = new long[n<<1];

        int k = 0, p = 0;
        for (int[] field : fields) {
            long x = field[0];
            long y = field[1];
            long r = field[2];

            xs[k++] = (x<<1) - r;
            xs[k++] = (x<<1) + r;
            ys[p++] = (y<<1) - r;
            ys[p++] = (y<<1) + r;
        }

        // xs数组中，排序了且相同值只留一份，返回有效长度
        int sizeX = sort(xs);
        // ys数组中，排序了且相同值只留一份，返回有效长度
        int sizeY = sort(ys);

        // 构造差分数组，n个力场，sizex : 2 * n, sizey : 2 * n
        int[][] diff = new int[sizeX + 2][sizeY + 2];
        for (int i = 0, a, b, c, d; i < n; i++) {
            long x = fields[i][0];
            long y = fields[i][1];
            long r = fields[i][2];

            a = rank(xs, (x<<1) - r, sizeX);
            b = rank(xs, (x<<1) + r, sizeX);
            c = rank(ys, (y<<1) - r, sizeY);
            d = rank(ys, (y<<1) + r, sizeY);

            add(diff, a, b, c, d);
        }

        int ans = 0;
        // O(n^2) 计算差分数组和
        for (int i = 1; i < diff.length; i++) {
            for (int j = 1; j < diff[0].length; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                ans = Math.max(ans, diff[i][j]);
            }
        }

        return ans;
    }

    // [50,70,30,70,30,60] 长度6
    // [30,30,50,60,70,70]
    // [30,50,60,70] 60 -> 3
    //  1  2  3  4
    // 长度4，
    public static int sort(long[] nums) {
        Arrays.sort(nums);
        int size = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[size - 1]) {
                nums[size++] = nums[i];
            }
        }
        return size;
    }

    public static int rank(long[] nums, long v, int size) {
        int l = 0;
        int r = size - 1;
        int m, ans = 0;
        while (l <= r) {
            m = (l + r) / 2;
            if (nums[m] >= v) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return ans + 1;
    }

    public static void add(int[][] diff, int a, int b, int c, int d) {
        diff[a][b] += 1;
        diff[c+1][d + 1] += 1;
        diff[a][d + 1] -= 1;
        diff[c+1][b] -= 1;
    }
}
